\chapter{Introduction}

\section{Motivation}
The number of miles travelled by vehicles on the UK's roads has doubled in
the last twenty-five years~\cite{dftTrafficLevels}. Road congestion 
is strongly correlated with increased road usage and now has a
large negative impact on many economies throughout the world: Road
congestion in the UK was estimated to cost the economy \pounds 12bn in
2004~\cite{dftFeasibilityPricing}; similarly, the cost in the US was \$63.1bn in
2003~\cite{texasUrbanMobilityRep05}. Meanwhile air pollution from traffic
is estimated to cost the UK as much as \$5 billion per annum, mainly
through ill health~\cite{UNEP:TrafficAirPollution}.

In the UK at least, flow data of vehicles is gathered on many motorways and
trunk roads. In contrast, towns and cities are more difficult to instrument
and therefore data quality is generally low, yet this is where congestion
and pollution affect most people. Existing Traffic Information Systems most 
often fail to provide accurate and timely information to drivers.  
Data collection and processing is also hampered by the tight integration of 
existing sensors and applications. For example, a system to measure flow rates of vehicles at busy junctions in the city of Cambridge, England has existed for many years. Unfortunately the data containing the detailed movements of vehicles is only used to schedule the length of time traffic lights are in the green phase, and once used, this data is thrown away. The London Congestion Charging system is another example; the perimeter of the city centre is monitored by a network of cameras that photograph all vehicles entering the zone. Automatic Number Plate Recognition software subsequently extracts vehicle licence plate data, which is used for billing purposes and then also thrown away. 

We believe that investment in monitoring, distribution and processing of
traffic information should result in a substantial and significant increase
in transport efficiency. Such data gathering and processing should enable
better strategic planning and encourage better use of public transport,
both of which would help cut pollution and congestion. This work will study
the problem of efficiently collecting and disseminating traffic information in urban settings.



\section{Our Model}


\subsection{Requirements for Traffic Data}
Traffic flow is characterized by a set of parameters including flow rate, speed, density, capacity and occupancy. These parameters assist in describing both uninterrupted streams of traffic, like uncongested freeways, and interrupted flow, as found on roads containing stop signs and signals. Some parameters are related to the flow of individual vehicles, providing a microscopic view of traffic, whereas others deal with the movement of groups of vehicles providing a macroscopic view. The measurement or mathematical derivation of these parameters can provide vital information, e.g. in order to decide whether a road is congested one has to examine the relationship between flow rate and density~\cite{Denos2002}. Speed, flow, and density are all related to each other. The relationships between speed and density are not difficult to observe in the real world, while the effects of speed and density on flow are not quite as apparent. Under uninterrupted flow conditions, speed, density, and flow are all related by the following equation:
\begin{center}
$q = k*v$
\end{center}
where 
$q = $Flow (vehicles/hour), 
$v = $Speed (miles/hour, kilometers/hour), 
$k = $Density (vehicles/mile, vehicles/kilometer).
These basic traffic-flow variables describe the state of a road system and measures such as delays, stops, travel time, total travel can be derived by a suitable application. For instance, in order to characterize a road segment as congested, a low flow value accompanied by a high density of vehicles are good indicators. 




\subsection{Physical Architecture}
\label{sec:sens}

Although existing traffic monitoring systems are small scale, isolated and application-specific, we believe this situation is likely to change in the near future given the rising public demand for accurate traffic data, especially in the context of route-planning efficiency. Stationary sensor infrastructures will continue to expand but, more importantly, vehicles will be equiped with wireless interfaces which, coupled with the increasing popularity of sattelite navigation systems, will enable them to participate in the sensing task as traffic sensors themselves. 

Our work focuses on the propagation of traffic information from sensor devices that are able to measure traffic quantities (e.g. speed and flow) to a Traffic Monitoring Centre (\emph{TMC}) where the sensor readings are centrally stored. We assume that the TMC is directly linked to a small number of \emph{Gateway} nodes, deployed  throughout the city. These nodes act as collection points for sensor readings. They are connected to a fixed power source and have plentiful bandwidth, storage, and processing capabilities. Gateway nodes feed data to the TMC through a backbone connection, essentialy forming the border between sensor networks and the applications that consume traffic data. 

We are considering two sensor classes throughout this work, stationary and mobile sensors.

\subsubsection{Stationary Sensors}
Stationary sensors are wireless sensor devices with traffic sensing capabilities placed at fixed locations in the field. We distinguish between two types of stationary sensors:
\begin{itemize}
\item{Permanent Sensors.}

These are roadside units whose installation is usually intrusive (infrared cameras, laser sensors, inductive loops) and their deployment requires a significant investment. They have a fixed power source and ample storage and processing capabilities. We believe it is not realistic to assume that they have a direct connection to the TMC since their widespread deployment in an urban setting would raise infrastructure costs prohibitively. We rather assume that they are equipped with wireless interfaces over which they communicate  with each other. It is assumed that such an infrastructure network will be sparse due to its costly deployment.

\item{Temporary Sensors.}

Sensor devices aimed for temporary deployments are portable and less costly to install. These are typically resource-constrained devices, with limited storage and processing capabilities, and are equipped with short range wireless interfaces. They incorporate non-intrusive sensor technology like magnetometers or acoustic sensors and can be battery-powered. 
\end{itemize}


\subsubsection{Mobile Sensors}
In this work we are also considering sensor units that do not form part of the fixed infrastructure. A mobile sensor is a wireless sensor device attached to a vehicle travelling within the urban sensing field. It is equiped or interfaced with a sattelite navigation system. The mobile sensor can communicate wirelessly with other mobile or stationary sensors, while the navigation system provides it with the following knowledge:
\begin{itemize}
\item Absolute location in the form of GPS coordinates.
\item Absolute speed.
\item Road topology through a preloaded digital map of the area.
\end{itemize}





\subsection{Quality of Service Requirements}
\label{sec:qos}
Sensors gather traffic data and propagate it to the Traffic Monitoring Centre \emph{(TMC)} , where it is centrally stored. This data is subsequently made available to various applications targeted at different groups of users. We consider two major classes of applications as consumers of traffic data:
\begin{enumerate}

\item{Route planning and emergency.

This class of applications might include route-planners for drivers that need to evaluate the expected travel time between two locations and decide on a suitable route to their destination, or emergency applications used by authorities to ease congestion incurred by a traffic accident by rerouting traffic via alternate roads. 
}

\item{Planning of future traffic infrastructures.

The second class of applications support planning, analysis and optimization of private and public transport management and are primarily used by local authorities, private and public operating companies and transport communities, as well as consultancies and industry. They are likely to be used to support decisions concerning calibrating traffic lights, identifying critical road intersections that would benefit from police forces deployment, deciding on where to assign one-way vs. two-way traffic, or determining suitable locations for points of interest, like museums and shopping malls. }
\end{enumerate}

Different applications impose different constraints on data freshness. The first class of applications require the most up-to-date traffic information in order to provide realistic travel plans and achieve low reaction times in emergency situations. On the other hand, applications of the second class typically operate on archived historical traffic data, and their output is not affected by the inclusion or not of the latest updates, e.g. the traffic readings of the current day. 

We are also considering precision requirements. Traffic applications, especially the second class we are considering, can certainly tolerate a small reduction in data precision. This relaxed precision requirement can be exploited to build more efficient dissemination algorithms. 




\subsection{Bandwidth Constraints}
\label{sec:bwlimit}
We assume that the network infrastructure, including stationary and mobile sensor nodes, will not be exclusive to the traffic monitoring application; it is likely be utilized by multiple applications that will have to compete for its resources. For instance, the stationary sensor network might also be used for pollution monitoring, temperature monitoring etc. The mobile network can be utilized to provide internet access to passengers, propagate advertisements about nearby places of interest, provide the driver with safety information (e.g. emergency braking) and so on. Bandwidth can therefore be assumed to be a scarce resource.

This matter is further aggravated if we take into account inter-system interference. This type of interference is of particular significance in wireless systems that operate in similar frequency bands, where it appears in the form of co-channel interference both among multiple users of the same technology and among different co-existing technologies. In~\cite{Golmie2001} it is shown that Bluetooth and WLAN, two widely used technologies in urban environments, are heavily interfering with each other. 

Some message dissemination schemes transmit more messages than others, either because they use multiple message copies, make different decisions about the next hop, or simply because of protocol overhead. The number of transmissions is a measure of the level of utilization of the wireless medium by a protocol. Hence it is necessary to design algorithms that are frugal in the use of the wireless channel during the propagation of traffic information from sensor nodes to gateways. 


\section{Objective}
\label{sec:objectives}
In order to study the dissemination of traffic data in an urban setting, we will investigate how traffic data can be propagated from the different available sensor types to the TMC where applications of the two main classes run. We will attempt to do so with minimal communication cost,  whilst adhering to the quality of service requirements imposed by the application. More formally, our goal is to answer long-running queries of the following form, whilst minimizing communication:
%\begin{mylisting}
\begin{verbatim}
  SELECT attribute FROM roadsegments 
   SENSE_EVERY sensingPeriod
   [REPORT_EVERY repPeriod]
   [REPORT_DELAY repDelay]
   [REPORT_ACCURACY repError]
\end{verbatim}
%\end{mylisting}
where \verb|attribute| refers to the measured traffic quantity (i.e. speed, flow, etc.) and \verb|roadsegments| to the sensors monitoring parts of the street network. \verb|sensingPeriod| denotes the sampling interval for  \verb|attribute| at each road segment and therefore effects data granularity.  The data freshness requirements of the application are reflected by  the values of \verb|repPeriod| and \verb|repDelay|; \verb|repPeriod| defines the frequency of data updates required by the application while \verb|repDelay| defines the delay that can be tolerated while doing so. The application relaxed precision requirements are defined in the \verb|REPORT_ACCURACY| clause by \verb|repError|. Notice that several query clauses are bracketed as those can be omitted depending on whether they are relevant to the scenario considered.

In this thesis we are going to explore two approaches to reducing communication:
\begin{enumerate}
\item{Energy-efficient routing algorithms}

We will devise routing algorithms that make smart forwarding decisions in order to deliver packets to gateways with few transmissions, rather than blindly and aggressively transmitting. 

\item{In-network data reduction}

Once an appropriate routing layer has been set up, we can further reduce the communication cost by performing operations on the sensed data. By exploiting patterns or knowledge about the data, we can perform efficient data reduction while data is routed towards the gateway. 
\end{enumerate}

\section{Scenarios}
\label{sec:scenarios}

We will pursue our main objective for all the different sensor types and application classes considered, in order to provide a holistic approach to traffic information dissemination. We will be studying three distinct scenarios that are realistic in this context and require seperate approaches. 
\subsubsection{Traffic Monitoring Using Stationary Sensors} 
\begin{description}
\item[Scenario 1]: Permanent Stationary Sensors

In this scenario we assume the existence of a permanent sensor infrastucture that can be used to monitor traffic. We aim to provide traffic information to both classes of applications that we discussed in Section~\ref{sec:qos}. While the two application classes may share similar \verb|sensingPeriod| requirements, the first class requires much more frequent data updates and thus imposes a \verb|repPeriod| constraint equal to \verb|sensingPeriod|. Typically applications in the first class will also tolerate less \verb|repError| than applications in the second class. Since the report period and accuracy requirements of the first class of applications are tighter than those of the second, they do not need to be considered seperately in this case; as long as the deployment provides data according to specification for consumption by applications in the first class, it should be more that adequate for the second class of applications. 

We assume that the the stationary sensor nodes form a connected wireless network with at least one gateway. A connected path, possibly over multiple hops, always exists from any sensor node to a gateway. For reasons presented in Section~\ref{sec:sens} we assume the network to be sparse. The network sparseness does not provide much choice routing-wise; each node has usually only a single parent in the routing tree that leads to the gateway, rendering tree-based routing the only viable choice. We will therefore focus on in-network data reduction to reach our objective in this scenario.



\item[Scenario 2]: Temporary Stationary Sensors

When a permanent stationary sensor infrastructure is in place it can provide traffic information to both application classes we are considering. However, the second class of applications, those that support future planning decisions, are mostly intended for parts of the transport network that need revision or are under development and where a stationary sensor infrastructure is likely to be absent. In this case traffic data collection is practical only by utilizing a temporary sensor deployment. We are therefore considering the scenario of deploying a temporary sensor network, specifically with the second class of applications in mind. 

By only considering the second class of applications, this scenario becomes unique in terms of quality of service requirements. As discussed in Section~\ref{sec:qos}, future planning applications operate on historical data and can tolerate late inclusion of recent readings. It is therefore not necessary to frequently forward sensor readings to the gateway. Thus, in this scenario we will use periodic data propagation with a large period (\verb|repPeriod|$>>$\verb|sensingPeriod|) which means more data is accumulated locally at the sensors at each period. This is the reason for considering this scenario seperately; the availability of a high amount of data enables us to use specialized, more efficient data reduction techniques than those of Scenario 1. 

\end{description}
\subsubsection{Traffic Monitoring Using Mobile Sensors} 
\begin{description}
\item[Scenario 3]: Mobile Sensors

In this scenario we are utilizing vehicles with navigation devices as sensors for traffic attributes and are thus dealing with a dynamic topology. Similarly to Scenario 1, we aim to provide data for both application classes. The network consists of vehicles travelling in the area which can communicate over wireless links when they are in range. Intermittent connectivity exists between two vehicles and between a vehicle and a gateway. Routing is not straighforward in this case and, in order to reach our objective, we have to begin our study in the routing layer. We will therefore focus on devising energy-efficient routing algorithms for this scenario as a first step. Following the development of an efficient routing protocol, we will investigate how traffic data can be acquired  in the mobile network context with respect to specific accuracy requirements.

\end{description}



\section{Outline}
The remainder of this report is organised in 4 chapters. Chapter 2 will provide an extensive review of literature that is related to our problem and objectives. In Chapter 3 we will present our work on traffic data propagation using a temporary sensor deployment (Scenario 2) and in Chapter 4 the work we will discuss our work on vehicular networks (Scenario 3). Finally, in Chapter 5 we will list the goals of our future work and define specific milestones towards their completion. We will conclude Chapter 5 with a detailed table of contents for the thesis. 















